home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Disc to the Future 2
/
Disc to the Future Part II Programmer's Reference (Wayzata Technology)(6013)(1992).bin
/
MAC
/
OTHER_LA
/
QUINTA
/
DICTIONA.C
< prev
next >
Wrap
Text File
|
1990-08-16
|
21KB
|
954 lines
/*
* Quinta ⌐ 1990 Eric W. Sink
*
* This file contains functions relating to the dictionary
*
*/
#include "Q_includes.h"
/*--------------------------------------------------------------------*/
int SingleAble(x, order)
long x;
int order;
{
register int index;
register int result;
result = 1;
index = 0;
while ((index < order) && result)
{
result = result && ((digit(x, index) == (**control_cp).ClassIndex)
|| (digit(x, index) == (**generic_cp).ClassIndex));
index++;
}
return result;
}
/*--------------------------------------------------------------------*/
int Comment(name, str)
char *name;
char *str;
{
MessageHandle msg;
newQstringp(str);
msg = findmessagep(name, 0);
if (((**msg).comment))
{
DropHandle((void **) ((**msg).comment));
}
(**msg).comment = popstr();
}
/*--------------------------------------------------------------------*/
long RespTableIndex(set)
ClassSet set;
{
register QInt index = 0;
register long result;
result = 0;
while ((*set)[index])
{
result = result * MaxClasses + (**(((*set)[index]))).ClassIndex;
index++;
if (index > MaxHomes) {
QERROR(diaggeneral);
}
}
return result;
}
/*--------------------------------------------------------------------*/
RespTagHandle *ParentPtr(x)
RespTagHandle x;
{
if ((**x).parent)
{
if ((**((**x).parent)).right == x)
{
return &((**((**x).parent)).right);
}
else
{
return &((**((**x).parent)).left);
}
}
else
{
return &((**((**((**x).r)).message)).responselist);
}
}
/*--------------------------------------------------------------------*/
int Rotate1Right(current, child)
RespTagHandle current;
RespTagHandle child;
{
(**current).right = (**child).left;
(**child).left = current;
(*(ParentPtr(current))) = child;
(**child).parent = (**current).parent;
(**current).parent = child;
}
/*--------------------------------------------------------------------*/
int Rotate1Left(current, child)
RespTagHandle current;
RespTagHandle child;
{
(**current).left = (**child).right;
(**child).right = current;
(*(ParentPtr(current))) = child;
(**child).parent = (**current).parent;
(**current).parent = child;
}
/*--------------------------------------------------------------------*/
int Rotate2Right(current, child, grandchild)
RespTagHandle current;
RespTagHandle child;
RespTagHandle grandchild;
{
(**current).right = (**grandchild).left;
(**child).left = (**grandchild).right;
(**grandchild).left = current;
(**grandchild).right = child;
(*(ParentPtr(current))) = grandchild;
(**grandchild).parent = (**current).parent;
(**current).parent = grandchild;
(**child).parent = grandchild;
}
/*--------------------------------------------------------------------*/
int Rotate2Left(current, child, grandchild)
RespTagHandle current;
RespTagHandle child;
RespTagHandle grandchild;
{
(**current).left = (**grandchild).right;
(**child).right = (**grandchild).left;
(**grandchild).right = current;
(**grandchild).left = child;
(*(ParentPtr(current))) = grandchild;
(**grandchild).parent = (**current).parent;
(**current).parent = grandchild;
(**child).parent = grandchild;
}
/*--------------------------------------------------------------------*/
int SetRespTablen(msg, n, resp)
MessageHandle msg;
long n;
ResponseHandle resp;
{
/* This has become a long routine... */
register QInt done;
register RespTagHandle x;
register RespTagHandle y;
register RespTagHandle last;
register RespTagHandle child;
register RespTagHandle grandchild;
register RespTagHandle current;
register RespTagHandle tr;
register RespTagHandle newtr;
if (SingleAble(n, (**msg).order) &&
((**msg).single != (ResponseHandle) - 1))
{
if (!(**msg).responselist)
{
(**msg).single = resp;
}
}
else
{
if ((**msg).single)
{
if ((**msg).single != (ResponseHandle) - 1)
{
if (resp != (**msg).single)
{
ResponseHandle temp;
temp = (**msg).single;
(**msg).single = (ResponseHandle) - 1;
(**msg).responselist = NULL;
AddTable2((**temp).HomesIndex, msg, temp, 1);
}
}
else
{
(**msg).single = NULL;
}
}
}
if ((**msg).single)
{
(**msg).RespCount = 1;
(**msg).responselist = NULL;
return;
}
/* If we made it to here, then the tree must be manipulated... */
/*
* First, find out if the node we seek is in the tree. After this
* loop, done == 1 indicates that the node does not exist. done==2
* indicates that the node was found and its handle is in x
*/
x = (**msg).responselist;
done = 0;
last = NULL;
while (!done)
{
if (x)
{
if (((**x).index) == n)
{
done = 2;
}
else if ((**x).index > n)
{
last = x;
x = (**x).left;
}
else
{
last = x;
x = (**x).right;
}
}
else
{
done = 1;
}
}
if (done == 2)
{
if (!resp)
{
/*
* if we set a resp to NULL, we really Delete the
* response
*/
if ((**x).r)
{ /* the else case should never happen */
child = x;
current = (**x).parent;
done = 0;
while (!done)
{
switch ((**current).condcode)
{
case 0:
if ((**current).right == child)
{
(**current).condcode = -1;
}
else
{
(**current).condcode = 1;
}
done++;
break;
case 1:
if ((**current).left == child)
{
/* step 3 */
switch ((**((**current).right)).condcode)
{
case 0:
Rotate1Right(current, child);
(**current).condcode = 1;
(**child).condcode = -1;
done++;
break;
case 1:
Rotate1Right(current, child);
(**current).condcode = 0;
(**child).condcode = 0;
current = child;
break;
case -1:
grandchild = (**child).left;
Rotate2Right(current, child, grandchild);
if (!(**grandchild).condcode)
{
(**current).condcode = 0;
(**child).condcode = 0;
}
else
{
if ((**grandchild).condcode == 1)
{
(**current).condcode = -1;
(**child).condcode = 0;
}
else
{
(**current).condcode = 0;
(**child).condcode = 1;
}
}
(**grandchild).condcode = 0;
current = grandchild;
break;
}
}
else
{
(**current).condcode = 0;
}
break;
case -1:
if ((**current).left == child)
{
(**current).condcode = 0;
}
else
{
/*
* step 4 - mirror image
* of above
*/
switch ((**((**current).left)).condcode)
{
case 0:
Rotate1Left(child, current);
(**current).condcode = 1;
(**child).condcode = -1;
done++;
break;
case 1:
Rotate1Left(child, current);
(**current).condcode = 0;
(**child).condcode = 0;
current = child;
break;
case -1:
grandchild = (**child).right;
Rotate2Left(child, current, grandchild);
if (!(**grandchild).condcode)
{
(**current).condcode = 0;
(**child).condcode = 0;
}
else
{
if ((**grandchild).condcode == 1)
{
(**current).condcode = -1;
(**child).condcode = 0;
}
else
{
(**current).condcode = 0;
(**child).condcode = 1;
}
}
(**grandchild).condcode = 0;
current = grandchild;
break;
}
}
break;
}
}
if ((**x).left)
{
if ((**x).right)
{
tr = (**x).left;
while ((**tr).right)
{
tr = (**tr).right;
}
newtr = tr;
}
else
{
newtr = (**x).left;
}
}
else
{
if ((**x).right)
{
newtr = (**x).right;
}
else
{
newtr = NULL;
}
}
(*(ParentPtr(x))) = newtr;
(**msg).RespCount--;
DropHandle((void **) x);
}
}
else
{
(**x).r = resp;
}
}
else
{
if (resp)
{
(**msg).RespCount++;
y = (RespTagHandle) GetHandle((Size) sizeof(RespTagStruct));
(**y).index = n;
(**y).r = resp;
(**y).parent = last;
(**y).condcode = 0;
(**y).left = NULL;
(**y).right = NULL;
if (last)
{
if ((**last).index > n)
{
(**last).left = y;
}
else
{
(**last).right = y;
}
}
else
{
(**msg).responselist = y;
}
/* Now rebalance the tree, if necessary */
x = (**y).parent;
child = y;
grandchild = NULL;
done = !x;
while (!done)
{
switch ((**x).condcode)
{
case 0:
if (child == (**x).right)
{
(**x).condcode = 1;
}
else if (child == (**x).left)
{
(**x).condcode = -1;
}
grandchild = child;
child = x;
x = (**x).parent;
done = !x;
break;
case 1:
if (child == (**x).right)
{
/* rebalance */
if (grandchild == (**child).right)
{
(**x).right = (**child).left;
(**child).left = x;
if ((**x).parent)
{
if ((**((**x).parent)).left == x)
{
(**((**x).parent)).left = child;
}
else
{
(**((**x).parent)).right = child;
}
}
else
{
(**msg).responselist = child;
}
(**child).parent = (**x).parent;
(**x).parent = child;
(**((**x).right)).parent = x;
(**x).condcode = 0;
(**child).condcode = 0;
}
else
{
(**x).right = (**grandchild).left;
(**grandchild).left = x;
(**child).left = (**grandchild).right;
(**grandchild).right = child;
if ((**x).parent)
{
if ((**((**x).parent)).left == x)
{
(**((**x).parent)).left = grandchild;
}
else
{
(**((**x).parent)).right = grandchild;
}
}
else
{
(**msg).responselist = grandchild;
}
(**grandchild).parent = (**x).parent;
(**child).parent = grandchild;
(**x).parent = grandchild;
(**((**x).right)).parent = x;
(**((**child).left)).parent = child;
if ((**y).index > (**grandchild).index)
{
(**child).condcode = -1;
(**x).condcode = 0;
}
else if ((**y).index < (**grandchild).index)
{
(**child).condcode = 0;
(**x).condcode = 1;
}
else
{
(**child).condcode = 0;
(**x).condcode = 0;
(**grandchild).condcode = 0;
}
}
}
else if (child == (**x).left)
{
(**x).condcode = 0;
}
done = 1;
break;
case -1:
if (child == (**x).right)
{
(**x).condcode = 0;
}
else if (child == (**x).left)
{
/* rebalance */
if (grandchild == (**child).left)
{
(**x).left = (**child).right;
(**child).right = x;
if ((**x).parent)
{
if ((**((**x).parent)).right == x)
{
(**((**x).parent)).right = child;
}
else
{
(**((**x).parent)).left = child;
}
}
else
{
(**msg).responselist = child;
}
(**child).parent = (**x).parent;
(**x).parent = child;
(**((**x).left)).parent = x;
(**x).condcode = 0;
(**child).condcode = 0;
}
else
{
(**x).left = (**grandchild).right;
(**grandchild).right = x;
(**child).right = (**grandchild).left;
(**grandchild).left = child;
if ((**x).parent)
{
if ((**((**x).parent)).right == x)
{
(**((**x).parent)).right = grandchild;
}
else
{
(**((**x).parent)).left = grandchild;
}
}
else
{
(**msg).responselist = grandchild;
}
(**grandchild).parent = (**x).parent;
(**child).parent = grandchild;
(**x).parent = grandchild;
(**((**x).left)).parent = x;
(**((**child).right)).parent = child;
if ((**y).index < (**grandchild).index)
{
(**child).condcode = 1;
(**x).condcode = 0;
}
else if ((**y).index < (**grandchild).index)
{
(**child).condcode = 0;
(**x).condcode = -1;
}
else
{
(**child).condcode = 0;
(**x).condcode = 0;
(**grandchild).condcode = 0;
}
}
}
done = 1;
break;
}
}
}
}
}
/*--------------------------------------------------------------------*/
ResponseHandle GetRespMn(msg, n)
MessageHandle msg;
long n;
{
register QInt done;
register RespTagHandle x;
register RespTagHandle last;
if (x = (RespTagHandle) (**msg).single)
{
return (ResponseHandle) x;
}
x = (**msg).responselist;
done = 0;
last = NULL;
while (!done)
{
if (x)
{
if (((**(x)).index) == n)
{
done = 2;
}
else if ((**x).index > n)
{
last = x;
x = (**x).left;
}
else
{
last = x;
x = (**x).right;
}
}
else
{
done = 1;
}
}
if (done == 2)
{
return (**x).r;
}
else
{
return NULL;
}
}
/*--------------------------------------------------------------------*/
long Hash1(s)
QStr s;
{
return (((char) (**s)) * ((long) (((long) (MaxTotalMessages / 128)) % (long) MaxTotalMessages)));
}
/*--------------------------------------------------------------------*/
#ifndef applec
long power(x, y)
long x, y;
{
if (y == 1)
{
return x;
}
else if (!y)
{
return (long) 1;
}
else
{
return x * power(x, y - 1);
}
}
#endif
/*--------------------------------------------------------------------*/
MessageHandle findmessage(name, create)
QStr name;
QInt create;
{
register QInt hashindex, startsearch;
register long index;
register long numresps;
register MessageHandle found;
hashindex = Hash1(name);
startsearch = hashindex - 1;
found = NULL;
while ((!found) && startsearch != hashindex)
{
if (((*GlobalMsgTable)[hashindex]))
{
if (!Qstrcmp(name, (**((*GlobalMsgTable)[hashindex])).name))
{
found = ((*GlobalMsgTable)[hashindex]);
}
else
{
hashindex = (hashindex + 1) % MaxTotalMessages;
}
}
else
{
hashindex = (hashindex + 1) % MaxTotalMessages;
}
}
if ((!found) && create)
{
found = (MessageHandle) GetHandle((Size) sizeof(messagenode));
(**found).name = (QStr) GetHandle((Size) MAXNAMELENGTH);
(**found).RespCount = 0;
(**found).RespMax = MaxClasses;
(**found).comment = NULL;
(**found).order = create;
(**found).TableIndex = MaxTotalMessages + 1;
numresps = (**found).RespMax;
(**found).responselist = NULL;
(**found).single = NULL;
Qstrcpy((**found).name, name);
(**found).status = 0;
AssignTableIndex(found);
}
return found;
}
/*--------------------------------------------------------------------*/
MessageHandle findmessagep(name, create)
char *name;
QInt create;
{
char *pointer;
pointer = name;
return findmessage(&pointer, create);
}
/*--------------------------------------------------------------------*/
MessageHandle killmessage(name)
QStr name;
{
MessageHandle temp;
MessageHandle found;
MessageHandle last;
found = findmessage(name, 0);
(*GlobalMsgTable)[(**found).TableIndex] = NULL;
DropHandle((void **) (**found).name);
if ((**found).comment)
{
DropHandle((void **) (**found).comment);
}
DropHandle((void **) found);
}
/*--------------------------------------------------------------------*/
QInt Inherited1(msg, n)
MessageHandle msg;
long n;
{
register long x, y;
register ResponseHandle r;
x = n;
y = -1;
if (r = GetRespMn(msg, n))
{
y = (**r).HomesIndex;
}
return (x != y);
}
/*--------------------------------------------------------------------*/
int CountResponses(tree)
RespTagHandle tree;
{
register ResponseHandle resp;
register int count;
count = 0;
if ((**tree).left)
{
count += CountResponses((**tree).left);
}
if ((**tree).right)
{
count += CountResponses((**tree).right);
}
resp = (**tree).r;
if (resp)
{
if (!Inherited1((**resp).message, (**tree).index))
{
count++;
}
}
return count;
}
/*--------------------------------------------------------------------*/
QInt NumDefined(index)
long index;
{
/*
* MultiMessage inheritance: a response can be passed to all subclasses
* simply by iterating over the subclasses and copying the response
* handle to all the apprpriate places in the RespTable for that Message.
* A given resptable entry can be determined if it was inherited or not
* by comparing the RespTableIndex of the entry with the RespTableIndex
* of the Homes Set in the Response Record. If not equal, the resp is
* inherited.
*/
MessageHandle msg;
msg = (*GlobalMsgTable)[index];
if ((**msg).single)
{
return 1;
}
else if ((**msg).responselist)
{
return CountResponses((**msg).responselist);
}
else
{
return 0;
}
}
/*--------------------------------------------------------------------*/
int remove_response(resp, oldresp)
ResponseHandle resp;
ResponseHandle oldresp;
{
MessageHandle msg;
ResponseHandle prev;
ResponseHandle dead;
ClassHandle cls;
register long index;
register long RespIndex;
msg = (**resp).message;
index = (**msg).TableIndex;
RespIndex = (**resp).HomesIndex;
SetRespTablen(msg, RespIndex, NULL);
if (oldresp)
{
AddTable2(RespIndex, msg, oldresp, 1);
}
if (!NumDefined(index))
{
killmessage((**msg).name);
}
if ((**resp).parms)
{
DropHandle((void **) (**resp).parms);
}
DropHandle((void **) resp);
}
/*--------------------------------------------------------------------*/
ResponseHandle newresponse(code, numparms)
int (*code) ();
QInt numparms;
{
register ResponseHandle result;
register long index;
result = (ResponseHandle) GetHandle((Size) sizeof(dictelement));
(**result).code = code;
(**result).status = 0;
(**result).HomesIndex = (long) 0;
(**result).message = NULL;
(**result).numparms = numparms;
if (numparms)
{
index = numparms;
(**result).parms = (MessageHandle **) GetHandle((Size) index * sizeof(MessageHandle));
while (index)
(*((**result).parms))[--index] = NULL;
}
else
{
(**result).parms = NULL;
}
return result;
}
/*--------------------------------------------------------------------*/
int insertresp(setindex, newdict, msg)
long setindex;
ResponseHandle newdict;
MessageHandle msg;
{
register QInt index;
(**newdict).HomesIndex = setindex;
(**newdict).message = msg;
AddTable2(setindex, msg, newdict, 1);
}
/*--------------------------------------------------------------------*/
int AssignTableIndex(msg)
MessageHandle msg;
{
register QInt resultindex = 0;
resultindex = Hash1((**msg).name);
if (((*GlobalMsgTable)[resultindex]))
{
while (((*GlobalMsgTable)[resultindex]))
resultindex = (resultindex + 1) % MaxTotalMessages;
}
(*GlobalMsgTable)[resultindex] = msg;
(**msg).TableIndex = resultindex;
}
/*--------------------------------------------------------------------*/
int AddTable2(respindex, msg, resp, toprecurs)
long respindex;
MessageHandle msg;
ResponseHandle resp;
QInt toprecurs;
{
register QInt index, index2;
register QInt clsindex;
register QInt tempdigit;
register long subindex;
register ClassSet mytempset;
register ClassSet subs;
ResponseHandle theresp;
theresp = GetRespMn(msg,respindex);
if (!theresp)
{
SetRespTablen(msg, respindex, resp);
}
else if ((respindex != ((**theresp).HomesIndex)) &&
((**theresp).HomesIndex == (**resp).HomesIndex) )
{
SetRespTablen(msg, respindex, resp);
}
else if (toprecurs)
{
SetRespTablen(msg, respindex, resp);
}
/* Then set for all subclasses */
if (!(**msg).single)
{
index2 = 0;
while (index2 < (**msg).order)
{
clsindex = 0;
tempdigit = digit((long) respindex, (short) index2);
subs = ((**((*ClassTable)[tempdigit])).subclasses);
while ((*subs)[clsindex])
{
subindex = subst((long) respindex, (short) index2,
(short) tempdigit,
(short) (**((*subs)[clsindex])).ClassIndex);
AddTable2(subindex, msg, resp, 0);
clsindex++;
}
index2++;
}
}
}
/*--------------------------------------------------------------------*/